// 排序算法

// 2.1　冒泡排序
// 冒泡排序的时间复杂度为O(n2)，但在最好的情况下能达到O(n)，因为它至少得“跑一趟”判定每个元素的位置是正确的。
// 比较第1个数与第2个数，将小数放在前面，大数放在后面。

// (2)	比较第2个数与第3个数，这时第2个数应该是第1个数和第2个数的最大值，它们会重复步骤(1)的行为，将大数放在后面，如此循环，直到倒数第1个数与倒数第2个数相比较，最后，末位的数是这个数组中的最大值。这是第一次遍历。
// (3)	开始下一次遍历，数组有n个元素，那么就该遍历次。

function bubbleSort1(array) {
    let n = array.length;
    for(let i = 1; i < n; i++) {
      for(let j = 0; j < n-i; j++) { // i增大，内层循环比较次数n-i减小
        if(array[j] > array[j+1]) { // 注意这里的索引变量都是j
          swap(array, j , j+1);
        }
      }
    }
}
// 这个方法非常常用，在其他章节中用到时会省略此方法
function swap(array, a, b ){
    let temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

// 优化方案1 

function bubbleSort2(array) {
    let n = array.length;
    for(let i = 1; i < n; i++){
      let hasSort = true;
      for(let j = 0; j < n-i; j++){
        if(array[j] > array[j+1]){ // 注意这里的索引变量都是j
          swap(array, j , j+1);
          hasSort = false;
        }
      }
      if(hasSort){
        break;
      }
    }
}

// 优化方案2

function bubbleSort3(array) {
    let n = array.length, k = n-1, swapPos = 0;
    for(let i = 1; i < n; i++) {
      let hasSort = true;
      for(let j = 0; j < k; j++) {
        if(array[j] > array[j+1]) { // 注意这里的索引变量都是j
          swap(array, j, j+1);
          hasSort = false;
          swapPos = j; // 记录交换位置，直接到内部循环最后一个被交换的元素
        }
      }
      if(hasSort) {
        break;
      }
      k = swapPos;// 重写内部循环的最后边界
    }
}

// 写一个程序，看一下我们的成果：

function shuffle(a) {
    let len = a.length;
    for (let i = 0; i < len - 1; i++) {
      let index = parseInt(Math.random() * (len - i));
      let temp = a[index];
      a[index] = a[len - i - 1];
      a[len - i - 1] = temp;
    }
  }
function test(sortFn) {
    let array = [];
    // 向数组写入10 000个数据，其中前1000个数据倒序，后9000个数据顺序
    for (let i = 0; i < 10000; i++) {
        if (i <= 1000) {
        array[i] = 1000 - i;
        } else {
        array[i] = i;
    }
}
console.log("========");
let start = new Date - 0;
sortFn(array);
console.log("部分有序的情况",sortFn.name, new Date - start);
shuffle(array);
start = new Date - 0;
sortFn(array);
console.log("完全乱序的情况",sortFn.name,new Date - start);    

}
function swap(array, a, b);  {/**略**/}
function bubbleSort1(array); {/**略**/}
function bubbleSort2(array); {/**略**/}
function bubbleSort3(array); {/**略**/}
test(bubbleSort1);
test(bubbleSort2);
test(bubbleSort3);


// 鸡尾酒排序
// 排序时是以双向在序列中进行排序的
function cocktailSort(array) {
    let left, right, index, i;
    left = 0; // 数组起始索引
    right = array.length - 1; // 数组索引最大值
    index = left; // 临时变量
  
    // 判断数组中是否有多个元素
    while (right > left) {
      let isSorted = false;
      // 每一次进入while循环，都会找出相应范围内最大最小的元素并分别放到相应的位置
      // 大的排到后面
      for (i = left; i < right; i++) { // 从左向右扫描
        if (array[i] > array[i + 1]) {
          swap(array, i, i + 1);
          index = i; // 记录当前索引
          isSorted = true;
        }
      }
      right = index; // 记录最后一个交换的位置
      // 小的放到前面
      for (i = right; i > left; i--) { // 从最后一个交换位置从右往左扫描
        if (array[i] < array[i - 1]) {
          swap(array, i, i - 1);
          index = i;
          isSorted = true;
        }
      }
      left = index; // 记录最后一个交换的位置
      if(!isSorted) {
        break;
      }
    }
}


// 2.2　选择排序

// 选择排序的行为与冒泡排序相反，它每一次遍历都是找到最小的数放在前面
// 冒泡排序与选择排序都会将当前数组划分为两个区域：有序区与无序区。冒泡排序的有序区在后面，选择排序的有序区在前面

function selectSort(array) {
    let n = array.length;
    for (let i = 0; i < n; i++) {
      let minIndex = i; // 保存当前最小数的索引
      for (let j = i + 1; j < n; j++) { // 每次只从i的后一个位置开始查找
        if (array[j] < array[minIndex]) {
          minIndex = j;   
        }
      }
      if (i !== minIndex) {
        swap(array, i, minIndex);
      }
    }
}

// 两端同时排序

function selectSort2(array) {
    let left = 0;
    let right = array.length-1;
    let min = left; // 存储最小值的下标
    let max = left; // 存储最大值的下标
    while (left <= right) {
      min = left;
      max = left;
      // 这里只能用<=，因为要取array[right]
      for (let i = left; i <= right; i++) {
        if (array[i] < array[min]) {
          min = i;
        }
        if (array[i] > array[max]) {
          max = i;
        }
      }
      swap(array, left, min);
      if (left == max) {
        max = min;
      }
      swap(array, right, max);
      left++;
      right--;
    }
}

test(bubbleSort1);
test(bubbleSort2);
test(bubbleSort3);
test(selectSort);
test(selectSort2);



// 2.3　插入排序
// 它类似选择排序，也是将数组划分为两个区域，左边的第1个数为有序区，右边的所有数在无序区。
// 不同的是，插入排序的每次循环不是找最小的数，而是直接将无序区的第1个数取出来，插入到有序区适当的位置上。
// 这样有序区不断扩大，无序区不断缩小，直到无序区内部为空。


function insertSort(array) {
    let n = array.length;
    for (let i = 1; i < n; i++) {
      let target = array[i];
      let j;
      for (j = i - 1; j >= 0; j--) { // ①查找：在有序区找到目标元素
        if (target > array[j]) {
          break;
        }
      }
      if (j !== i - 1) {
        // 将比target大的所有元素都后移一位
        for (let k = i - 1; k > j; k--) { // ②挪坑：挪到位置，留出坑位
          array[k + 1] = array[k];
        }
        array[j + 1] = target;
      }
    }
}

// 查找和挪坑这两步合并
// y[i] >= array[i - 1]，说明array[0...i]也是有序的，无须调整。
// 否则就令j = i - 1，target = array[i]。
// 然后一边将array[j]向后移动，一边向前搜索，当有array[j] < array[i]时，停止，
// 并将target放到array[j + 1]处

function insertSort(array) {
  let n = array.length;
  for (let i = 1; i < n; i++) {
    let target = array[i];
    // 合并两个内部循环
    for (let j = i - 1;  j >= 0 && array[j] > target;  j--) {
      array[j + 1] = array[j]; // 挪出坑位
    }
    array[j + 1] = target; // 放入坑位
  }
}
// while
function insertSort2(array) {
  let n = array.length;
  for (let i = 1; i < n; i++) { // ［i,n－1］是无序区
    let target = array[i];
    while (j > 0 && array[j-1] > target) {
      array[j] = array[j-1]; // 前面的覆盖后面的
      j--;
    }
    array[j] = target; // 放入坑位
  }
}

// 插入排序的时间复杂度也是O(n2)，但是经过测试后发现，在大多数情况下，插入排序比前两种排序的性能更高，这是因为它的平均复杂度为O(n2/4) ，最好的情况下能达到O(n)



// 2.4　希尔排序

// 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法，是插入排序的改进版，也称为缩小增量排序，
// 同时它是第一批冲破的算法之一

// 因为在1959年以前，涌现过众多排序算法，思路迥异，各显神通，但都无法突破的天花板。当时，插入排序已经算是非常优秀的算法了，排序算法不可能突破的声音成为主流。
// 但是希尔排序的出现改变了这一切


// 该算法的基本思想是：将原数组切割成几个子数组，每个子数组是由索引值相差某个增量gap的元素组成，
// 对这些子数组分别进行插入排序，然后减少增量，重新划分大数组为新的子数组，
// 继续对子数组们进行直接插入排序，直到增量为1。


// 希尔排序的分组法就是为了减少交换次数而发明的。



// 增量序列

// 每趟用到的增量gap，共同组成一个数组，称为间隔序列
// 间隔序列由Knuth提出，通过递归表达式 h = 3 * h + 1 来产生，数列的第1项为1，代入公式产生4，4再产生13，13再产生40…… 
// 当元素大于排序数组的长度时，我们就中止这个递归


function shellSort(array) {
  // 生成增量序列 3x+1 [1, 4, 13, 40, 121, 364, 1093, 3280, 9841] 
  let n = array.length,
      gaps = [1],
      gap = 1;
  while (true) {
    gap = gap * 3 + 1;
    if(gap >= n){// 根据定义：增量不能大于数组长度
      break;
    }
    gaps.push(gap);
  }
  while (gap = gaps.pop()) {
    // 对每个子数组进行排序
    for (let g = 0; g < gap; g++) {
      // 正常的插入排序
      for (let i = g + gap; i < n; i += gap) {
        let target = array[i]; // 从无序区取元素
        if (target < array[i - gap]) {
          // 无序区的元素比有序区的小
          let j = i;
          while (j > 0 && array[j - gap] > target) {
            array[j] = array[j - gap]; // 将前面的元素覆盖后面的
            j -= gap;// 不是-1而是-gap
          }
          array[j] = target;
        }
      }
      // 正常的插入排序
    }
  }
  console.log(array);
}

// 希尔排序没有规定增量公式，随着公式的不同，其时间复杂度也不一样。因此，希尔排序是一种不稳定的排序。在希尔的原稿中，他建议初始的间距为n/2，简单地把每一趟排序分成了两半。
// 因此，对于n=100的数组，逐渐减小的间隔序列为50,25,12,6,3,1.

function shellSort2(array) {
  // 希尔序列 [1, 2, 4, 9, 19, 39, 78, 156, 312, 625, 1250, 2500, 5000] 
  let n = array.length,
      gaps = [],
      gap = n;
  while (gap != 1) {
    gap = gap >> 1; // 相当于 Math.floor(n/2)
    gaps.unshift(gap);
  }
  while (gap = gaps.pop()) {
    // 对每个子数组进行排序
    // 正常的插入排序
  }
}

// 希尔排序的排序效率和增量序列有直接关系，相关增量序列如下。
// (1)	希尔（Shell）序列：N / 2，N / 4，...，1（重复除以2）。
// (2)	希伯德（Hibbard）序列：1，3，7，...，2 k1。
// (3)	克努特（Knuth）序列：1，4，13，...，（3 k1）/ 2。
// (4)	塞奇威克（Sedgewick）序列：1，5，19，41，109，... 
// 目前最好的序列是塞奇威克序列，它能让希尔排序的复杂度达到 O()，快于O(nlog2n) 的堆排序，其计算公式：

function getSedgewickSeq(n) {
  let startup1 = 0, startup2 = 2, array = [];
  for (let i = 0; i < n; i++) {
    if (i % 2 == 0) {
      array[i] = 9 * Math.pow(4, startup1) - 9 * Math.pow(2, startup1) + 1;
      startup1++;
    } else {
      array[i] = Math.pow(4, startup2) - 3 * Math.pow(2, startup2) + 1;
      startup2++;
    }
    if (array[i] >= n) {
      break;
    }
  }
  return array;
}

function shellSort3(array) {
  // 生成增量序列 [1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001] 
  let n = array.length,
      gaps = getSedgewickSeq(n),
      gap = 1;
  // 略
}

test(selectSort);
test(selectSort2);
test(insertSort2);
test(shellSort);
test(shellSort2);
test(shellSort3);



// 2.5　归并排序

// 希尔排序给我们带来一个新思路，将一个问题拆分成几个小规模的子问题，然后用现成的方案解决这些子问题，再慢慢合并来解决原问题。
// 人们后来将这种解题思路称为分治法。

// (1)	分解：将原问题分解成一系列子问题。
// (2)	解决：递归地求解各子问题。若子问题足够小，则直接求解。
// (3)	合并：将子问题的结果合并成原问题的解。


function mergeArray(arrA, arrB) {
  
  let lengthA = arrA.length - 1, 
      lengthB = arrB.length - 1,
      mergedArr = [], 
      IndexA = 0, 
      IndexB = 0, 
      indexMerged = 0;
  while (IndexA <= lengthA - 1 && IndexB <= lengthB - 1) {
    // 先比较两个数组等长的部分，看谁的元素较小，谁就先进合并数组
    mergedArr[indexMerged++] = arrA[IndexA] < arrB[IndexB] ? arrA[IndexA++] : arrB[IndexB++];
  }
  // 可能是B数组先遍历完，此时A数组还有剩余
  while (IndexA <= lengthA - 1) {
    mergedArr[indexMerged++] = arrA[IndexA++];
  }
  // 也可能是A数组先遍历完，此时B数组还有剩余
  while (IndexB <= lengthB - 1) {
    mergedArr[indexMerged++] = arrB[IndexB++];
  }
  return mergedArr;
} 

// 给数组元素添加top、left、right属性，用来分别引用切割后的子数组及其父数组
// 处于合并阶段，当数组的长度为1
// 往上一级进行数组合并 toMerge = true
// 合并时，每个元素都要找它的邻居元素。首先它要知道自己是在左边还是右边，
// 然后再找它的邻居。对它的邻居也要判定一下是否有序。当一个数组的长度为1，
// 或者已经被调整过，我们就为它添加一个属性array.sorted = true。
// 这样，传参数组就与邻居进行了合并，否则它可能还处于分割状态

function mergeSort(array, toMerge) {
  // 如果数组还可以分割，并且处于分割模式
  if (array.length > 1 && toMerge !== true) {
    let top = array;
    let mid = array.length >> 1;
    top.left = array.slice(0, mid);
    top.right = array.slice(mid);
    top.left.top = top;
    top.right.top = top;
    console.log(top.left, top.right, "分割");
    mergeSort(top.left);
    mergeSort(top.right);
    // 如果数组只剩下一个或者处于合并模式
  } else if (array.length === 1 || toMerge) {
    if (array.top && !array.merged) { // 如果左边合并了右边，那么右边就不用再合并左边
      let isLeft = array === array.top.left;
      let neighbor = isLeft ? array.top.right : array.top.left;
      if (neighbor.length === 1 || neighbor.sorted) {
        let temp = mergeArray(array, neighbor);
        neighbor.merged = true; // 已经合并
        console.log(temp, "合并");
        for (let i = 0, n = temp.length; i < n; i++) {
          array.top[i] = temp[i];
        }
        array.top.sorted = true;
        mergeSort(array.top, true);
      }
    }
  }
}

let array = [3, 4, 9, 1, 8, 2, 0, 7, 6, 5];
mergeSort(array);

// 优化。 虚拟数组

function mergeSortObject(array) {
  function sort(obj, toMerge) {
    // 如果数组还可以分割，并且处于分割模式
    let { array, begin, end } = obj;
    let n = end - begin;
    if (n !== 0 && toMerge !== true) {
      let mid = begin + ((end - begin) >> 1);
      obj.left = {
        begin: begin,
        end: mid,
        array: array,
        top: obj,
      }
      obj.right = {
        begin: mid + 1,
        end: end,
        array: array,
        top: obj,
      }
      sort(obj.left);
      sort(obj.right);
      // 如果数组只剩下一个或者处于合并模式
    } else if (n === 0 || toMerge) {
      if (obj.top && !obj.merged) { // 如果左边合并了右边，那么右边就不用再合并左边
        let top = obj.top;
        let isLeft = obj === top.left;
        let neighbor = isLeft ? top.right : top.left;
        if ((neighbor.end == neighbor.begin) || neighbor.sorted) {
          let temp = mergeArrayByIndex(array, begin, end, neighbor.begin, neighbor.end);
          neighbor.merged = true;// 表明已经合并
          let b = top.begin;
          for (let i = 0, n = temp.length; i < n; i++) {
            array[b + i] = temp[i];
          }
          top.sorted = true;
          sort(top, true);
        }
      }
    }
  }
  sort({
    array: array,
    begin: 0,
    end: array.length - 1,
  });
  return array;
}


// mergeArray方法也要改造一下，改造后的mergeArrayByIndex代码如下：

function mergeArrayByIndex(arr, begin, end, begin2, end2) {
  let indexA = begin, indexB = begin2, indexMerged = 0, mergedArr = [];
  while (indexA <= end && indexB <= end2) {
    // 先比较两个数组等长的部分，看谁的元素较先，谁就先进c数组
    mergedArr[indexMerged++] = arr[indexA] < arr[indexB] ? arr[indexA++]: arr[indexB++];
  }
  // 略
  return mergedArr;
}


// 进一步

function mergeSortObject2(array) {
  function sort(obj, toMerge) {
    // 如果数组还可以分割，并且处于分割模式
    let { array, begin, end } = obj;
    let n = end - begin;
    if (n !== 0 && toMerge !== true) {
      let mid = begin + ((end - begin) >> 1);
      obj.left = {
        begin: begin,
        end: mid,
        array: array,
      }
      obj.right = {
        begin: mid + 1,
        end: end,
        array: array,
      }
      sort(obj.left);
      sort(obj.right);
      let temp = mergeArrayByIndex(array, begin, mid, mid + 1, end);
      for (let i = 0, n = temp.length; i < n; i++) {
        array[begin + i] = temp[i];
      }
    }
  }
  sort({
    array: array,
    begin: 0,
    end: array.length - 1,
  });
  return array;
}

// 我们发现sort方法的第1个参数obj可以由对象改回数组，第2个参数toMerge也可以不要了。优化后的代码如下：

function mergeSortSimple(array) {
  // 如果数组还可以分割，并且处于分割模式
  function sort(array, begin, end) {
    // 如果数组还可以分割，并且处于分割模式
    if (begin !== end) {
      let mid = begin + ((end - begin) >> 1);
      sort(array, begin, mid);
      sort(array, mid + 1, end);
      let temp = mergeArrayByIndex(array, begin, mid, mid + 1, end);
      for (let i = 0, n = temp.length; i < n; i++) {
        array[begin + i] = temp[i];
      }
    }
  }
  sort(array, 0, array.length - 1);
  return array;
}


// 最后，我们看一下它的复杂度。其空间复杂度为O（n）;
// 最初的版本，创建了这么多数组，其空间复杂度可能就是
// 我们每次要取中位数，导致一共对层进行了切割合并的操作。
// 每一层归并操作的时间复杂度都是O(log n)，所以这个算法的时间复杂度是
// O(nlog n)

// 2.6　堆排序

// 2.7　快速排序
// 快速排序（quick sort）是对冒泡排序的一种改进，是又一个基于分治法的排序。
// 它不像归并排序那样“一下子”将数组切成“碎片”，而是逐渐对要处理的数组进行分割，
// 每次切成两部分，让其左边都小于某个数，右边都大于某个数，然后对这左右两部分继续进行相同的处理（快速排序）
// ，直到每个子数组的长度为1，原数组即可完全有序.

function quickSort(array) {
  function QuickSort(array, left, right) {
    if (left < right) {
      let index = partition(array, left, right);
      QuickSort(array, left, index - 1);
      QuickSort(array, index + 1, right);
    }
  }
  QuickSort(array, 0, array.length - 1);
  return array;
}

function partition(array, left, right) {// 分治函数
  // todo
}


// quickSort是一个入口函数，它调用某个递归子程序QuickSort。

// QuickSort内部有一个partition函数，它会选中某个元素作为枢轴（pivot，分界值），实现对子数组的左右切割，保证左边的元素都比pivot小，右边的元素都比pivot大，最后返回pivot的索引值，方便再对左右数组调用QuickSort。

// 2.7.1　快速排序的常用方法

// 1. 左右指针法

// (1)	选取某个元素作为pivot，一般取当前数组的第一个元素或最后一个元素，这里采用最后一个元素。
// (2)	从left一直向后寻找，直到找到一个大于pivot的值，而right则从后至前寻找，直至找到一个小于pivot的值，然后交换这两个元素的位置。
// (3)	重复第(2)步，直到left和right相遇，这时将pivot放置在left的位置即可。


function partition(array, left, right) { // 分治函数
  let pivot = array[right];
  let pivotIndex = right;
  while (left < right) {
    while (left < right && array[left] <= pivot) {
      // 1. 防止越界需要left < right
      // 2. array[left] <= pivot 因为可能存在相同元素
      left++; // 找到比pivot大的数
    }
    while (left < right && array[right] >= pivot) {
      right--; // 找到比pivot小的数
    }
    swap(array, left, right);
  }
  // 最后一个比pivot大的left元素要与pivot相交换
  swap(array, left, pivotIndex);
  return left; // 返回的是中间的位置
}
console.log(quickSort([4, 1, 7, 6, 9, 2, 8, 0, 3, 5]));


// 2. 挖坑法
// 挖坑法实现partition方法的步骤如下：
// (1)	选取某个元素作为pivot，这里选择第1个元素，将它“挖”出来（这只是概念上的挖，它两边的数不会趁机占领这位置）。于是这个位置就是最初的“坑”。
// (2)	从left一直向后寻找，直到找到一个大于pivot的值，然后将该元素放入坑中，坑位变成了array[left]。
// (3)	从right一直向前寻找，直到找到一个小于pivot的值，然后将该元素放入坑中，坑位变成了array[right]。
// (4)	重复(2)和(3)的步骤，直到left和right相遇，然后将pivot放入最后一个坑位，返回最后一个坑位的位置。

function partition(array, left, right) {
  let pivot = array[right]; // 坑位为array[right]
  while (left < right) {
    while (left < right && array[left] <= pivot) {
      left++;
    }
    array[right] = array[left]; // 坑位变成array[left]
    while (left < right && array[right] >= pivot) {
      right--;
    }
    array[left] = array[right]; // 坑位变成array[right]
  }
  array[right] = pivot;
  return left;
}
// array[left] -> array[right] -> array[left] -> array[right]……


// 3. 前后指针法
// 定义两个指针，一前一后，前面的指针寻找比pivot小的元素，
// 后面的指针寻找比pivot大的元素。前面的指针找到符合条件的元素后，
// 将前后指针所指向的数据进行位置交换，当前面的指针遍历完整个数组时，
// 将pivot与后指针的后一位进行数据交换，然后返回后指针的位置

function partition(arr, left, right) {
  let cur = left; // 找大数
  let prev = cur - 1; // 找小数
  let pivot = arr[right];
  while (cur <= right) {
    if (arr[cur] <= pivot && ++prev != cur)
      swap(arr, prev, cur);
    cur++;
  }
  return prev;
}

// 最大的优势就是支持对链表的排序，而左右指针法和挖坑法则只能针对数组进行排序。


// 2.7.2　快速排序的优化
// (1)	优化选取枢轴。
// 最好情况和最坏情况的区别就是选取枢轴不正确造成的。所以我们可以优化选取枢轴
// 三数取中法，即随机取3个元素进行排序，然后将中间数作为枢轴，一般我们选取左端、右端和中间3个数。网上有数据证明，使用三数取中法可以有效减少预排序输入的不利情形，
// 并且相比于优化前的快速排序，比较次数减少了大约14%。

// (2)	优化不必要的交换
// 我们将pivot备份到A[0]中，像在前文中使用swap方法时一样，我们只需要做替换的工作，最终A[i]和A[j]融合，
// 再将A[0]位置的数值赋值回A[i]。
// 因为这里没有了多次交换数据的操作，在性能上又得到了部分提高。

// (3)优化小数组时的排序方案。
// 对于很小的和部分有序的数组，快速排序不如插入排序好。当待排序序列的长度分割到一定大小后，
// 继续分割的效率比插入排序要差，此时可以使用插入排序

// 小数组使用插入排序的代码：
if (high - low + 1 < 10) {  
  insertSort(arr,low,high);  
  return;  
} else {
  quickSort(arr,low,high);
}

// 完整代码如下：
function getMid(array, left, right) {
  let mid = left + ((right - left) >> 1);
  if (array[left] <= array[right]) {
    if (array[mid] < array[left]) {
      return left;
    } else if (array[mid] > array[right]) {
      return right;
    } else {
      return mid;
    }
  } else {
    if (array[mid] < array[right]) {
      return right;
    } else if (array[mid] > array[left]) {
      return left;
    } else {
      return mid;
    }
  }
}

// 左右指针法
function partition(array, left, right) {
  let mid = getMid(array, left, right);
  swap(array, mid, right);
  let key = array[right];
  let keyIndex = right;
  while (left < right) {
    while (left < right && array[left] <= key) { // 因为有可能有相同的值，防止越界，所以加上left < right
      left++;
    }
    while (left < right && array[right] >= key) {
      right--;
    }
    swap(array, left, right);
  }
  swap(array, left, keyIndex);
  return left;
}
// 挖坑法(其他两种分治函数也一样，都是在最前面加两行)
function partition(array, left, right) {
  let mid = getMid(array, left, right);// 优化求pivot的方式
  swap(array, mid, right); 
  let key = array[right]; // 坑位为array[right]
  while (left < right) {
    while (left < right && array[left] <= key) {
      left++;
    }
    array[right] = array[left]; // 坑位为array[left]
    while (left < right && array[right] >= key) {
      right--;
    }
    array[left] = array[right]; // 坑位为array[right]
  }
  array[right] = key;
  return right;
}



// 2.7.3　非递归实现
// 递归的算法主要是在划分子区间，如果要非递归实现快速排序，只要使用一个栈来保存区间就可以了。
// 要将递归程序改成非递归程序，首先想到的就是使用栈，因为递归本身就是一个压栈（即向一个栈插入新元素，也可称为进栈、入栈）的过程。下面是快速排序的非递归实现：
function quickSort(array, start, end) {
  let stack = [];
  stack.push(end);
  stack.push(start);
  while (stack.length) {
    let l = stack.pop();
    let r = stack.pop();
    let index = partition(array, l, r);
    if (l < index - 1) {
      stack.push(index - 1);
      stack.push(l);
    }
    if (r > index + 1) {
      stack.push(r);
      stack.push(index + 1);
    }
  }
}


// 2.7.4　算法比较
// 快速排序是二叉查找树的一个空间优化版本。但它不是循序地把数据项插入到一个显式的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法产生了完全相同的比较次数，但是顺序不同。
// 快速排序的最直接竞争者是堆排序。堆排序通常会慢于原地排序的快速排序，其最坏情况的运行时间总是 。快速排序尽管通常情况下会比较快，但仍然会有最坏情况发生。
// 快速排序也会与归并排序竞争。归并排序的特点是最坏情况下仍然有着运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序算法，并且非常灵活，其设计可以应用于操作链表或大型链式存储等，例如磁盘存储或网络附加存储等。尽管快速排序也可以被重写并用在链表上，但对于基准的选择总是个问题。归并排序的主要缺点是在最佳情况下还需要的额外空间，而快速排序的原地分区和尾部递归仅使用的空间。


// 2.7.5　快速排序的一些应用
// TopK问题之1
// 我们知道，分治函数partition会返回一个pivot，在pivot左边的数都比第pivot个位置上的数小，在pivot右边的数都比第pivot个位置上的数大。
// 我们不妨不断调用分治函数，直到它输出的pivot = k-1，此时pivot前面的k个数（0到k1）就是要找的前k个数。相关代码如下：

function partition(array, left, right) { /**挖坑法**/}

function getTopK(array, k) {
  if (array.length >= k) {
    let low = 0;
    let high = array.length - 1;
    let pivot = partition(array, low, high);
    // 不断调整分治的位置，直到pivot = k-1
    while (pivot != k - 1) {
      // 大了，往前调整
      if (pivot > k - 1) {
        high = pivot - 1;
        pivot = partition(array, low, high);
      }
      // 小了，往后调整
      if (pivot < k - 1) {
        low = pivot + 1;
        pivot = partition(array, low, high);
      }
    }
    let ret = [];
    for (let i = 0; i < k; i++) {
      ret[i] = array[i];
    }
    return ret;
  }
  throw "数组长度必须>=" + k;
}
let ret = getTopK([11, 9, 6, 17, 0, 1, 2, 18, 3, 4, 8, 5], 4);
console.log(ret); // [0,1,2,3]


// 2.8　计数排序
// 前面介绍的都是比较排序，换言之，我们都需要在排序过程中比较两个元素的大小，它们的时间复杂度顶多到达。

// 接下来，我们看另外三种神奇的排序算法。用这3种算法的话，如果我们排序的对象是纯数字，时间复杂度还可以达到惊人的。

// 计数排序需要占用大量空间，它仅适用于数据比较集中的情况，比如 [0~100]、[10 000~19 999]这样的数据。
// 接下来我们看一下计数排序是怎么运作的。假设我们有[1, 2, 3, 1, 0, 4]这六个数，这里面最大的值为4，那么我们创建一个长度为4的数组，每个元素默认为0。这相当于选举排序，一共有6个投票桶，1就投1号桶，0就投0号桶。注意，这些桶本来就已经排好序了，并且桶的编号就代表原数组的元素。当全部投完时，0号桶有1个，1号桶有2个，2号桶有1个，3号桶有1个，4号桶有1个。然后我们将这些桶的所有数字依次拿出来，放到新数组，就神奇地排好排序了。
// 计数排序没有对元素进行比较，只是利用了桶与元素的一一对应关系，根据桶已经排好序的先决条件，解决排序。下述代码即对[9, 8, 5, 7, 16, 8, 6, 13, 14]进行了计数排序。

function countSort(arr) {
  let buckets = [],
    n = arr.length;
  for (let i = 0; i < n; i++) {
    let el = arr[i];
    buckets[el] = buckets[el] ? buckets[el] + 1 : 1;
  }
  console.log(buckets);// 测试
  let index = 0;
  // 遍历所有桶
  for (let i = 0; i < buckets.length; i++) {
    let time = buckets[i];
    while (time) { // 如果这桶不为空，那么我们可以对这桶操作time次
      arr[index] = i; // 将索引当作元素，覆盖index这个位置
      ++index;
      time--;
    }
  }
  return arr;
}
let arr = countSort([9, 8, 5, 7, 16, 8, 6, 13, 14]);
console.log(arr);

// 但这里存在几个问题。
// (1)	如果要排序的数组的最小元素不是从0开始的，如上例，那么桶数组的开始部分就会出现许多空元素。
// (2)	数组的索引值是从0开始的，意味着我们的元素也要大于或等于0。如果出现负数的情况，怎么办呢？ 
// 因此，完整的步骤如下。
// (1)	找出当前数组中的最大值和最小值。
// (2)	统计数组中每个值为i的元素出现的次数，存入数组buckets的第i项。
// (3)	对所有的计数累加（从buckets中的第一个元素开始，每一项和前一项相加）。
// (4)	反向遍历原数组：将每个元素i放在新数组的buckets(i)项，每放一个元素就将buckets(i)减去1。
// 解决上述问题后，计数排序的代码如下：

function countSort(arr) {
  let max = arr[0], min = arr[0], n = arr.length;
  for (let i = 0; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  let size = max - min + 1;
  let buckets = new Array(size).fill(0);
  // 遍历所有桶
  for (let i = 0; i < n; i++) {
    buckets[arr[i] - min]++;
  }
  for (let i = 1; i < size; i++) {
    // 求前缀和
    buckets[i] += buckets[i - 1];
  }
  let ret = [];// 逆向遍历源数组（保证稳定性）
  for (let i = n - 1; i >= 0; i--) {
    buckets[arr[i] - min]--;
    ret[buckets[arr[i] - min]] = arr[i];
  }
  return ret;
}

console.log(countSort([1, 0, 3, 1, 0, 1, 1]));
console.log(countSort([0, 5, 3, 2, 2]));
console.log(countSort([-2, -5, -45]));

// 2.9　桶排序
// 桶排序与计数排序很相似，不过现在的桶不单单只是为了计数，而是实实在在地放入元素。举个例子，学校要对所有老师按年龄进行排序，这么多老师很难操作，那么先让他们按年龄段进行分组，20~30岁的一组，30~40岁的一组，50~60岁的一组，然后组内再排序。这样效率就大大提高了。桶排序也是基于这种思想。
// 桶排序的操作步骤如下。
// (1)	找出当前数组中的最大值和最小值。
// (2)	确认需要多少个桶（这个通常作为参数传入，不能大于原数组长度），然后最大值减最小值，除以桶的数量，能得出每个桶最多能放多少个元素，我们称这个数为桶的最大容量。
// (3)	遍历原数组的所有元素，除以这个最大容量，就能得到它要放入的桶的编号了。在放入时可以使用插入排序，也可以在合并时再使用快速排序。
// (4)	对所有桶进行遍历，如果桶内的元素已经排好序，直接一个个取出来，放到结果数组就行了。
// 将数组 array 划分为n个大小相同的子区间（桶），每个子区间各自排序，最后合并。这样说是不是和分治法有点像啊！因为分治法就是分解——解决——合并这样的模式，可以理解为桶排序是一种特殊的分治法。
// 桶排序的代码如下：

function bucketSort(array, num) {
  if(array.length <= 1) {
    return array;
  }
  let n = array.length;
  let min = Math.min.apply(0, array);
  let max = Math.max.apply(0, array);
  if(max === min){
     return array;
  }
  let capacity = (max - min + 1) / num;
  let buckets = new Array(max - min + 1);
  for(let i = 0; i < n; i++){
    let el = array[i];// el可能是负数
    let index = Math.floor((el - min) / capacity);
    let bucket = buckets[index];
    if(bucket){
      let jn = bucket.length;
      if(el >= bucket[jn-1]){
        bucket[jn] = el;
      }else{
      // insertSort: 
      for(let j = 0; j < jn; j++) {
        if(bucket[j] > el) {
          while(jn > j) { // 全部向后挪一位
            bucket[jn] = bucket[jn-1];
            jn--;
          }
          bucket[j] = el; // 让el占据bucket[j]的位置
          break insertSort;
        }
      }
    }
    }else{
      buckets[index] = [el];
    }
  }
  let index = 0
  for(let i = 0; i < num; i++){
    let bucket = buckets[i]
    for(let k = 0, kn = bucket.length; k < kn; k++){
      array[index++] = bucket[k]
    }
  }
  return array;
}
let arr = [2,5,3,0,2,8,0,3,4,3];
console.log(bucketSort(arr,4));
// [ 0, 0, 2, 2, 3, 3, 3, 4, 5, 8 ]



// 2.10　基数排序
// 基数排序是一种非比较型的整数排序算法。其基本原理是，按照整数的每个位数上的值进行分组。在分组过程中，对于不足位的数据用0补位。
// 基数排序按照对位数分组的顺序的不同，可以分为LSD（least significant digital）基数排序和MSD（most significant digital）基数排序。
// LSD基数排序，是按照从低位到高位的顺序进行分组排序的。MSD基数排序，是按照从高位到低位的顺序进行分组排序的。上述两种方式不仅仅是对位数的分组顺序不同，其实现原理也是不同的。


// 2.10.1　LSD基数排序
// LSD基数排序对于序列中每个整数的每一位都可以看成一个桶，而该位上的数字就可以认为是这个桶的键值。比如下面的数组：
// [170, 45, 75, 90, 802, 2, 24, 66];
// 首先，我们要确认最大值，一个for循环的最大数，因为最大数的位数最长。
// 然后，建立10个桶，亦即10个数组。
// 然后再遍历所有元素，取其个位数，个位数是什么就放进对应编号的数组，如1放进1号桶，遍历结果如下：
// 0号桶：170，90。1号桶：无。2号桶：802，2。3号桶：无。4号桶：24。5号桶：45，75。6号桶：66。7－9号桶：无。
// 然后依次将元素从桶里取最出来，覆盖原数组，或放到一个新数组，我们把这个经过第一次排序的数组叫sorted：
// sorted = [170,90,802,2,24,45,75,66];
// 然后我们再一次遍历sorted数组的元素，这次取十位的值。这时要注意，2不存在十位，那么默认为0：
// 0号桶：2，802。1号桶：无。2号桶：24。3号桶：无。4号桶：45。5号桶：无。6号桶：66。7号桶：170，75。8号桶：无。9号桶：90。
// 再全部取出来：
// sorted = [2，802,24，45，66，170，75，90];
// 开始百位上的入桶操作，没有百位就默认为0：
// 0号桶：2，24，45，66，75，90。1号桶：170。2－7号桶：无。8号桶：802。9号桶：无。
// 再全部取出来：
// sorted = [2，24，45，66，75，90，170，802];
// 没有千位数，那么循环结束，返回结果桶sorted。

// LSD基数排序的代码如下：
function radixSort(array) {
  let max = Math.max.apply(0, array);
  let times = getLoopTimes(max),
      len = array.length;
  let buckets = [];
  for (let i = 0; i < 10; i++) {
    buckets[i] = []; // 初始化10个桶
  }
  for (let radix = 1; radix <= times; radix++) {
    // 个位、十位、百位、千位这样循环
    lsdRadixSort(array, buckets, len, radix);
  }
  return array;
}
// 根据数字某个位数上的值得到桶的编号
function getBucketNumer(num, d) {
  return (num + "").reverse()[d];
}
// 或者这个
function getBucketNumer(num, i) {
  return Math.floor((num / Math.pow(10, i)) % 10);
}
// 获取数字的位数
function getLoopTimes(num) {
  let digits = 0;
  do {
    if (num > 1) {
      digits++;
    } else {
      break;
    }
  } while ((num = num / 10));
  return digits;
}
function lsdRadixSort(array, buckets, len, radix) {
  // 入桶
  for (let i = 0; i < len; i++) {
    let el = array[i];
    let index = getBucketNumer(el, radix);
    buckets[index].push(el);
  }
  let k = 0;
  // 重写原桶
  for (let i = 0; i < 10; i++) {
    let bucket = buckets[i];
    for (let j = 0; j < bucket.length; j++) {
      array[k++] = bucket[j];
    }
    bucket.length = 0;
  }
}
// test
let arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];
console.log(radixSort(arr));



// 2.10.2　MSD基数排序
// 接下来，讲MSD基数排序。最开始时也是遍历所有元素，取最大值，得到最大位数，建立10个桶。这时从百位取起。不足三位，对应位置为0。
// 0号桶： 45, 75, 90, 2, 24, 66。1号桶：107。2-7号桶：无。8号桶：802。9号桶：无。
// 接下来就与LSD不一样了。我们对每个长度大于1的桶进行内部排序。内部排序也是用基数排序。我们需要建立另10个桶，对0号桶的元素进行入桶操作，这时比原来少一位，亦即十位。
// 0号桶：2。1号桶：无。2号桶：24。3号桶：无。4号桶：45。5号桶：无。6号桶：66。7号桶：75。8号桶：无。9号桶：90。
// 然后继续递归上一步，因为每个桶的长度都没有超过1，于是开始0号桶的收集工作：
// 0号桶：2，24，45，66，75，90。1号桶：107。2-7号桶：无。8号桶：802。9号桶：无。
// 将这步应用于后面的其他桶，最后就能排序完毕。

// MSD基数排序的代码如下：
function radixSort(array) {
  let max = Math.max.apply(0, array),
      times = getLoopTimes(max),
      len = array.length;
  msdRadixSort(array, len, times);
  return array;
}

// 或者这个
function getBucketNumer(num, i) {
  return Math.floor((num / Math.pow(10, i)) % 10);
}
// 获取数字的位数
function getLoopTimes(num) {
  let digits = 0;
  do {
    if (num > 1) {
      digits++;
    } else {
      break;
    }
  } while ((num = num / 10));
  return digits;
}
function msdRadixSort(array, len, radix) {
  let buckets = [[], [], [], [], [], [], [], [], [], []];
  // 入桶
  for (let i = 0; i < len; i++) {
    let el = array[i];
    let index = getBucketNumer(el, radix);
    buckets[index].push(el);
  }
  // 递归子桶
  for (let i = 0; i < 10; i++) {
    let el = buckets[i];
    if (el.length > 1 && radix - 1) {
      msdRadixSort(el, el.length, radix - 1);
    }
  }
  let k = 0;
  // 重写原桶
  for (let i = 0; i < 10; i++) {
    let bucket = buckets[i];
    for (let j = 0; j < bucket.length; j++) {
      array[k++] = bucket[j];
    }
    bucket.length = 0;
  }
}
let arr = radixSort([170, 45, 75, 90, 802, 2, 24, 66]);
console.log(arr);


// 2.10.3　字符串使用基数排序实现字典排序
// 此外，基数排序并不局限于数字，稍作变换，就能应用于字符串的字典排序中。我们先来举一个简单的例子，只对都是小写字母的字符串数组进行排序。
// 小写字母一共26个，考虑到长度不一样的情况，我们需要对够短的字符串进行补充，这时补上什么好呢？我们不能直接补0，而是应该补空白。然后根据字母与数字的对应关系，建立27个桶，空字符串对应0，a对应1，b对应2……字典排序是从左边开始比较，因此我们需要用到MSD基数排序。
// 字符串使用基数排序实现字典排序代码如下：

let character = {};
"abcdefghijklmnopqrstuvwxyz".split("").forEach(function(el, i) {
  character[el] = i + 1;
});
function toNum(c, length) {
  let arr = [];
  arr.c = c;
  for (let i = 0; i < length; i++) {
    arr[i] = character[c[i]] || 0;
  }
  return arr;
}
function getBucketNumer(arr, i) {
  return arr[i];
}

function radixSort(array) {
  let len = array.length;
  let loopTimes = 0;

  // 求出最长的字符串，并得到它的长度，那也是最高位
  for (let i = 0; i < len; i++) {
    let el = array[i];
    let charLen = el.length;
    if (charLen > loopTimes) {
      loopTimes = charLen;
    }
  }

  // 将字符串转换为数字数组
  let nums = [];
  for (let i = 0; i < len; i++) {
    nums.push(toNum(array[i], loopTimes));
  }
  // 开始多关键字排序
  msdRadixSort(nums, len, 0, loopTimes);
  // 变回字符串
  for (let i = 0; i < len; i++) {
    array[i] = nums[i].c;
  }
  return array;
}

function msdRadixSort(array, len, radix, radixs) {
  let buckets = [];
  for (let i = 0; i <= 26; i++) {
    buckets[i] = [];
  }
  // 入桶
  for (let i = 0; i < len; i++) {
    let el = array[i];
    let index = getBucketNumer(el, radix);
    buckets[index].push(el);
  }
  // 递归子桶
  for (let i = 0; i <= 26; i++) {
    let el = buckets[i];
    // el.c是用来识别是桶还是我们临时创建的数字字符串
    if (el.length > 1 && !el.c && radix < radixs) {
      msdRadixSort(el, el.length, radix + 1, radixs);
    }
  }
  let k = 0;
  // 重写原桶
  for (let i = 0; i <= 26; i++) {
    let bucket = buckets[i];
    for (let j = 0; j < bucket.length; j++) {
      array[k++] = bucket[j];
    }
    bucket.length = 0;
  }
}
let array = ["ac", "ee", "ef", "b", "z", "f", "ep", "gaaa", "azh", "az",  "r"];

let a = radixSort(array);
console.log(a);